#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN=2e7+5,p=998244353;
int c,T;
int n,m,x[MAXN],y[MAXN];
signed main() {
	freopen("oi.in","r",stdin);
	freopen("oi.out","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>c>>T;
	if(c<=2) {
		while(T--) {
			cin>>n>>m;
			int cnt=0,xx[20],yy[20],dis[7][7];
			for(int i=1;i<=m;++i) cin>>x[i]>>y[i];
			for(int i=1;i<n;++i) {
				for(int j=i+1;j<=n;++j) {
					xx[cnt]=i,yy[cnt]=j;
					++cnt;
				}
			}
			int ans=1e9,tot=0;
			for(int i=0;i<(1<<cnt);++i) {
				if(__builtin_popcount(i)==m-1) {
					for(int j=1;j<=n;++j) {
						for(int k=1;k<=n;++k) {
							dis[j][k]=1e7;
						}dis[j][j]=0;
					}
					for(int j=0;j<cnt;++j) {
						if(i>>j&1) {
							dis[xx[j]][yy[j]]=dis[yy[j]][xx[j]]=1;
						}
					}
					for(int k=1;k<=n;++k) {
						for(int ii=1;ii<=n;++ii) {
							for(int jj=1;jj<=n;++jj) {
								dis[ii][jj]=min(dis[ii][jj],dis[ii][k]+dis[k][jj]);
							}
						}
					}
					int sum=0;
					for(int j=1;j<=m;++j) sum+=dis[x[j]][y[j]];
					if(sum<ans) ans=sum,tot=0;
					if(ans==sum) ++tot;
				}
			}
			cout<<-ans<<' '<<tot<<endl;
		}
	}
	else if(c<=4) {
		while(T--) {
			cin>>n>>m;
			for(int i=1;i<=m;++i) cin>>x[i]>>y[i];
			int ans=1;
			for(int i=3;i<=n;++i) ans=1ll*ans*i%p;
			cout<<-2*(n-1)<<' '<<ans<<endl;
		}
	}
	return 0;
}
